\documentclass[paper=a4, fontsize=11pt]{scrartcl}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{datetime}
\usepackage{fourier}
\usepackage{amsmath} % Formulas
\usepackage{enumerate} % Lists
\usepackage{graphicx} % Pictures
\usepackage{listings} % Allows code inclusions
\usepackage{titlesec} % Allows to offset section numbers

\definecolor{CustomColor}{rgb}{0.2,0.4,0.5}
\titlelabel{\llap{\thetitle\enskip}} % Offset section numbers
%\renewcommand{\thesubsection}{\alph{subsection})} % Subsection letters instead of numbers
\renewcommand{\ttdefault}{pcr} % Courier tt font has bold for code
\renewcommand{\dateseparator}{-}

\newcommand{\code}[2]{ % Include code using \code{Python}{filename.py}
    \lstset{
        language=#1,
        morekeywords={lambda, with, as, lambda},
        basicstyle=\small\ttfamily,
        stringstyle=\color{CustomColor},
        showstringspaces=false,
        commentstyle=\color{CustomColor}\textit,
        tabsize=4,
        numbers=left,
        numbersep=1em,
        numberstyle=\color{CustomColor},
    }
    \lstinputlisting{#2}
}
\newcommand{\codelines}[4]{ % Include code using \code{Python}{filename.py}
    \lstset{
        language=#1,
        firstnumber=#3,
        basicstyle=\footnotesize\ttfamily,
        stringstyle=\color{CustomColor},
        showstringspaces=false,
        commentstyle=\color{CustomColor}\textit,
        tabsize=8,
        numbers=left,
        numbersep=1em,
        numberstyle=\color{CustomColor},
        breaklines=false,
    }
    \lstinputlisting[firstline=#3, lastline=#4]{#2}
}

\setlength{\parskip}{0.15cm}
\setlength{\parindent}{0cm}
%------------------------------------------------------------------------------

\title{Information Retrieval Lab 7}
\author{Carlos García Márquez}
\date{\small\yyyymmdddate\today}

\begin{document}

%------------------------------------------------------------------------------

\maketitle

Tot el codi està al fitxer \texttt{ main.py}, que consta de tres parts.
\par
Primer el procés dels fitxers font. Les estructures de dades són vectors amb els noms dels aeroports, localització, etc. Aquests tenen mida lineal respecte al nombre d'aeroports. Els trajectes es guarden en un \textit{map} de \textit{maps} de mida variable, la mida total depèn del nombre total de trajectes diferents, no és una matriu (no és quadratic). Sobre l'eficiència, es podria millorar usant alguna estructura més especialitzada que el \textit{map} de la llibreria standard de Python, com una llista enllaçada, però milloraria un factor constant i seguiria sent lineal respecte l'entrada. De fet anava a fer servir una llibreria de grafs i al final no ha estat necessari.
\par
La segona part és el càlcul del PageRank. La única optimització que he fet és acumular el PageRank dels aeroports sense cap sortida, com es distribueix per igual entre tots els nodes es pot fer la suma i al final de tot incrementar cada node el valor acumulat entre el nombre d'aeroports (segurament és veu més clar al codi, línia 62).
\par
Fent una prova ràpida amb 10 decimals de precisió, es pot veure que la iteració a la que s'atura depenent del factor de damping no és lineal:
\begin{center}
    \begin{tabular}{ | l | l | l | l | l | l | l |}
    \hline
    factor & 0.75 & 0.80 & 0.85 & 0.90 & 0.95 & 0.99 \\ \hline
    iteració & 39 & 45 & 57 & 74 & 100 & 240 \\ \hline
    \end{tabular}
\end{center}
\par
Finalment s'imprimexen els resultats. Al fitxer \texttt{ results.txt} hi ha un exemple de sortida amb damping 0.85. Al fitxer \texttt{ graph.html} es pot visualitzar un graf amb els 50 aeroports amb major PageRank, els trajectes entre ells i el PageRank de cadascún. El gràfic el genera el fitxer \texttt{ main-html.py} que val més no mirar...
\begin{figure}[ht!]
    \centering
    \includegraphics[width=\textwidth]{1.png}
\end{figure}
\par
\section{Resultat}
\codelines{}{results.txt}{1}{50}

%------------------------------------------------------------------------------

\end{document}
